package leetcode.code1081;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	// "oaudghifjclknzmvxsb"
	// "oaubdfghijclknzmvxs"
	// okausidfnasdfbasbdfbasdfbasdgvlaksdjvlasdhfajbnsdkfashidfbasdkflvjnxcvlknzxmcvaxndhfkasdhfcbacdcbc
	public String smallestSubsequence(String s) {
		char[] stack = new char[s.length()];
		int[] hash = new int[128];
		for (int i = 0; i < stack.length; i++) {
			hash[s.charAt(i)]++;
		}
		boolean[] exist = new boolean[128];
		int p = 0;
		for (int i = 0; i < stack.length; i++) {
			char c = s.charAt(i);
			while (!exist[c] && p > 0 && c < stack[p - 1] && hash[stack[p - 1]] > 0) {
				exist[stack[p - 1]] = false;
				p--;
			}
			if (!exist[c]) {
				exist[c] = true;
				stack[p++] = c;
			}
			hash[c]--;
		}
		return new String(stack, 0, p);
	}

	@Override
	public void debug4() {
		H.compare("oaubdfghijclknzmvxs", this.smallestSubsequence(
				"okausidfnasdfbasbdfbasdfbasdgvlaksdjvlasdhfajbnsdkfashidfbasdkflvjnxcvlknzxmcvaxndhfkasdhfcbacdcbc"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int size = 100;
		char[] test = new char[size];
		for (int i = 0; i < size; i++) {
			int r = (int) (Math.random() * 26) + 'a';
			test[i] = (char) r;
		}
		System.out.println(new String(test));
	}

}
